package Offer;

import java.util.HashSet;

/*
    找出数组中重复的数字。
    在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
    来源：力扣（LeetCode）
    链接：https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class T03_findRepeatNumber {
//    法一：借助hashset的去重功能
//    时间复杂度O(n) 空间复杂度O(n)
    public int findRepeatNumber_1(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (set.contains(num)) {
                return num;
            }else {
                set.add(num);
            }
        }
        return 0;
    }

//   法2：创建一个数组来记录每个元素出现的次数，初始值为-1，每遍历到一个元素，先判断count[index]的值是否为-1，如果是，修改为0
//    否则就找到重复的元素了，和hashset方法类似，代码略


//    法3：原地排序
//    遍历数组，将元素i放在它正确序号的位置即nums[i],在交换前，如果另外一个位置的元素已经是正确的位置了
//    说明该元素重复了
//    时间复杂度O(n) 空间复杂度O(1)
    public int findRepeatNumber_2(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != i) {
                if (nums[nums[i]] != nums[i]) {
                    swap(nums, i, nums[i]);
                }else {
                    return nums[i];
                }
            }
        }
        return -1;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
